//顺序表基本运算算法
#include <stdio.h>
#define MAXL 100		//最大长度
typedef int KeyType;	//定义关键字类型为int
typedef char InfoType;

typedef struct
{	KeyType key;		//关键字项
	InfoType data;		//其他数据项，类型为InfoType
} RecType;				//查找元素的类型

void swap(RecType x,RecType y)	//x和y交换
{
	RecType tmp=x;
	x=y; y=tmp;
}

void CreateList(RecType R[],KeyType keys[],int n)	//创建顺序表
{
	for (int i=0;i<n;i++)			//R[0..n-1]存放排序记录
		R[i].key=keys[i];
}
void DispList(RecType R[],int n)	//输出顺序表
{
	for (int i=0;i<n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}



void ShellSort(RecType R[],int n) //希尔排序算法
{	int i,j,d;
	RecType tmp;
	d=n/2;					//增量置初值
	while (d>0)
	{
		for(int k = 0;k<d;k++)
		{
			for(i=0;i+d<n;i+=d)
			{
				for(j=0;j<n-d-i;j+=d)
				{
					if(R[j+k].key>R[j+d+k].key)
					{
						tmp = R[j+k];
						R[j+k] = R[j+d+k];
						R[j+d+k] = tmp;
					}
				}
			}
		}
		printf("  d=%d: ",d); DispList(R,n);
		d=d/2;				//减小增量
	}
}
int main()
{
	printf("(2)修改希尔排序算法,组内用冒泡排序实现。\n");
	int n=10;
	RecType R[MAXL];
	KeyType a[]={9,8,7,6,5,4,3,2,1,0};
	CreateList(R,a,n);
	printf("排序前:"); DispList(R,n);
	ShellSort(R,n); 
	printf("排序后:"); DispList(R,n);
	return 1;
}


